import java.util.ArrayList;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;

/**
 * @author VernHe
 * @date 2021年06月06日 18:29
 */
public class Solution_0139 {
    public static void main(String[] args) {
//        System.out.println("leetcode".substring(0, 8));
//        System.out.println("leetcode".substring(3));
        List<String> list = new ArrayList<>();
        list.add("leet");
        list.add("code");
        new Solution_0139().wordBreak("leetcode", list);
    }

    public boolean wordBreak(String s, List<String> wordDict) {
        HashSet<String> hash = new HashSet<>(wordDict);
        // dp[i]表示前i个字符是否可以被切分成单词
        byte[] dp = new byte[s.length() + 1];
        dp[0] = 1;

        for (int i = 1; i < dp.length; i++) {
            // j在 0-i 之间，是前i个字符串被切割的位置
            for (int j = 0; j < i; j++) {
                if (dp[j] == 1 && hash.contains(s.substring(j, i))) {
                    dp[i] = 1;
                    break;
                }
            }
        }
        return dp[s.length()] == 1;
    }

    /**
     * 记忆化搜索未完成
     * @param s
     * @param wordDict
     * @param memo
     * @param start
     * @return
     */
    private boolean canBreak(String s, List<String> wordDict, byte[] memo, int start) {
        if (s.length() == 0) {
            return true;
        }
        // 在字符串中找是否有匹配的
        for (int i = start + 1; i <= s.length(); i++) {
            System.out.println("当前字符串：" + s.substring(start,i) + "当前循环次数：" + (i + 1));
            // 如果前i个字符可以组成单词，并且后面的也可以组成单词就按返回true
            if (wordDict.contains(s.substring(start, i))) {
                memo[i] = 1;
                System.out.println(s.substring(start, i) + "是单词");
                String newStr = s.substring(i);
                if (memo[i] == 1 || canBreak(s, wordDict, memo, i)) {
                    return true;
                }
            }
        }
        return false;
    }
}
